Statecharts are a recently proposed visual formalism for the behavioral description of complex systems. They are described in Harel, D., Statecharts: A Visual Approach to Complex Systems, Science of Computer Programming (also, Weizmann Institute of Science, CS84-05, February 1984, Revised, December 1984). They extend standard state diagrams in several crucial ways, and enable modular, hierarchial descriptions of system behavior in top-down, bottom-up, or mixed fashions. Statecharts were suggested as a convenient formalism for describing the behavior of reactive hardware components, enabling powerful hierarchial representations and flexible concurrency and synchronization descriptions.
Statecharts appear to be a natural extension to the classical and well-known medium of state diagrams (or finite state machines--FSM's), which have been used extensively as an abstract model for digital control units, as discussed widely in Mead C. and Conway L., Introduction to VLSI Systems, Addison Wesley, 1980. Two well-known variations of the finite state model are the Moore and Mealy machines which have typical implementations using PLA's (programmable logic arrays) for the implementation of the combinatorial logic. PLA's enable simple and regular implementations of control units but have the price of being highly area-consuming as the number of states grows. This causes them to consume more power producing larger delays which force the designers to reduce clock frequencies.
The problem of large PLA's motivated the development of several techniques for PLA optimization. Two examples of such optimizations are: (1)PLA folding Hachtel, G. D., Techniques for Programmable Logic Array Folding, 19'th Design Automation Conf., June 1982, pp. 147-155; and (2) PLA partitioning, Ullman, J. D. Computational Aspects of VLSI, Computer Science Press, 1984. Both techniques, when considered in their full generality, are NP-complete, and thus heuristics are required for them to work in practice. An attempt to reduce PLA sizes using hierarchy can be found in Ayers, R., Silicon Compilation--A Hierarchical Use of PLA's In: 16'th Design Automation Conf., June 1979, pp. 314-326, utilizing a rather low level description language. Hierarchy is recommended in the above-cited Mead C. and Conway L. publication as a technique for reducing the complexity of system design but is used in conventional computers only in a limited way.
Another major problem concerning the FSM model is its limited ability to treat concurrency, a feature discussed widely in Drusinsky, D. Harel D., Using Statecharts for Hardware Description, Weizmann Institute of Science, CS85-06, June 1985.